1. Field of the Invention
The present invention relates to real-time resource scheduling, more specifically, to a method and apparatus for the real-time scheduling of a shared resource in an information system such as in digital communications between terminals of a communications network.
2. The Prior Art
When two computers wish to communicate with each other, they do so via a communications network. Networks are composed of computers and other terminal devices, such as printers, (collectively, computers) that are interconnected by electrical or optical cables. The capacity of a cable, also called its bandwidth, is measured in bits per second. The sum of the bit rates over all connections supported at one time by a cable cannot exceed its capacity.
Many networks are networks within networks, that is, larger networks composed of smaller networks connected together. For example, a company may have a local area network (LAN) in one of its offices that ties together all of the computers in that office. It then has a wide area network (WAN) that ties together the local networks of all of its offices. The company WAN may then be connected to a larger WAN, such as the Internet, a global network of thousands of smaller networks and computers. Generally, a network is connected to another network at one point, the gateway, where a hardware device, the interworking unit (IWU), acts as a translator between the different communications protocols and bit rates of the connected networks.
In general, information transferred from one computer to another over a network is not sent continuously. The information is broken up into segments, called packets, each of which is prefixed with a header and sent. The header may contain various information, such as the address of the source computer, the address of the destination computer, and the position of the packet in the totality of information sent from the source to the destination. The later is necessary when it cannot be assumed that all the packets will reach the destination by the same route, implying that the packets may arrive at the destination in a different order than they are sent. In the typical network, the amount of time that it takes to transmit each packet is the packet transmission interval, and is determined by dividing the length of the packet, in bits, by the bit rate of the network.
With the proliferation in the number and power of computers and the desire for computers to communicate at increasingly higher speeds, network bit rates must continue to increase to keep up with the demand for their services. Some WAN lines currently run at bit rates of up to 2.4 Gb/s using asynchronous transmission mode (ATM) standards, with higher rates anticipated. In an ATM system, each information packet is sent as a series of fixed-size cells. At 2.4 Gb/s, a 53-octet ATM cell has a cell interval of (53 octets*8 bits/octet)/2.4 Gb/s=176 nanoseconds (ns).
When it is desired to send information from a source system to a destination system, a virtual connection (VC) is set up. A VC is a logical connection between the systems. The physical transmission path (which may include electrical wires, optical fibers, and intervening computers) will often have segments that are shared by several VC's. Of course, the physical medium used for each segment must provide sufficient bandwidth to meet the requirements of all VC's set up through it.
In a segment of a transmission path, packets can be transferred synchronously or asynchronously. In synchronous transfer mode (STM), data is transferred within equal time periods, or frames, which are themselves composed of time slots. The number of time slots in each frame typically is the same as the maximum number of VC's. A VC that passes through an STM segment is assigned one slot within the frame. Consequently, all channels using this transmission segment have the same fixed bandwidth, regardless of actual need. If the fixed bandwidth is more than is necessary for the VC, some of the bandwidth is wasted. Conversely, if the fixed bandwidth is less than is necessary, some information may be lost.
In asynchronous transfer mode (ATM), there are no frames. Packets are allocated time slots when needed. Consequently, each VC only uses the bandwidth that it needs. When a system wishes to send information over an ATM network, it sends a request to the network controller for a VC that will run at a specified bandwidth. The VC is allocated and the interval of time between cells necessary to meet the bandwidth requirement, the rate period, is determined. Then the cells are sent one at a time during an access interval, called a cell interval in communications systems, separated by the rate period. The network controller must determine which cell to assign to each cell interval. Because the number and assignments of VC's change dynamically, it is not generally possible to make cell interval assignments in advance. Thus, each cell interval assignment must be made in real time during the previous cell interval, which means that the transmitting unit only has the amount of time in a cell interval (176 ns in the 2.4 Gb/s example above) to make the next assignment.
In present day ATM transmission equipment, the scheduling of transmission of ATM cells is typically implemented using a scheduling table that contains an arbitrary number of entries. Each entry in the table specifies a particular virtual channel (VC) and each VC may appear in many entries of the table. Sometimes, the table has a hierarchical structure. The scheduler cycles through the table repeatedly, processing one entry every cell interval. This method is simple, but has several problems, including the difficulty of maintaining the table as VC's become active or inactive, and the limited accuracy of the channel period due to the finite size of the table.